#ifndef _ABOUT_STRING_
#define _ABOUT_STRING_

#include <Vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class AboutString {
public:
    string replaceSpace( string s ) {

        std::size_t found = s.find_first_of( ' ' );

        while ( found != s.npos ) {
            s.replace( found, 1, "%20" );
            found = s.find_first_of( ' ', found + 1 );
        }

        return s;
    }

    string reverseLeftWords( string s, int n ) {

        string cut = s.substr( 0, n );
        string str = s.substr( n, s.size() - n );

        return str + cut;
        // return s.substring(n) + s.substring(0, n);
    }

    // my solution
    char firstUniqChar( string s ) {

        vector< char > letters;
        vector< int >  nums;
        bool           flag;

        for ( size_t i = 0; i < s.size(); i++ ) {
            flag = true;
            for ( size_t j = 0; j < letters.size(); j++ ) {
                if ( letters[ j ] == s[ i ] ) {
                    nums[ j ]++;
                    flag = false;
                    break;
                }
            }

            if ( flag ) {
                letters.push_back( s[ i ] );
                nums.push_back( 1 );
            }
        }

        for ( size_t i = 0; i < nums.size(); i++ ) {
            if ( nums[ i ] == 1 ) {
                return letters[ i ];
            }
        }
        return ' ';
    }

    /*借助队列找到第一个不重复的字符。队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素
     */
    char firstUniqChar2( string s ) {
        unordered_map< char, int > mapC;
        queue< char >              q;

        for ( size_t i = 0; i < s.size(); i++ ) {
            pair< unordered_map< char, int >::iterator, bool > pair = mapC.insert( make_pair< char, int >( char( s[ i ] ), 1 ) );

            if ( pair.second == true ) {
                q.push( char( s[ i ] ) );
            }
            else {
                pair.first->second = -1;
                while ( !q.empty() && mapC[ q.front() ] == -1 ) {
                    q.pop();
                }
            }
        }

        return q.empty() ? ' ' : q.front();
    }

    // array
    char firstUniqChar3( string s ) {
        unordered_map< char, int > map;

        pair< unordered_map< char, int >::iterator, bool > pair;

        for ( size_t i = 0; i < s.size(); i++ ) {
            pair = map.insert( make_pair< char, int >( char( s[ i ] ), 1 ) );
            if ( !pair.second ) {
                pair.first->second++;
            }
        }
        for ( size_t i = 0; i < s.size(); i++ ) {
            if ( map[ s[ i ] ] == 1 ) {
                return s[ i ];
            }
        }
        return ' ';
    }

    // 剑指 Offer 38.
    vector< string > permutation( string s ) {
        vector< int > used = vector< int >( s.size(), false );
        string        a    = "";
        dfspermutation( s, a, used );
        return m_permutation;
    }
    void dfspermutation( const string& str, string& result, vector< int >& used ) {
        set< char > set;
        if ( result.size() < str.size() ) {
            for ( size_t i = 0; i < str.size(); i++ ) {
                if ( !used[ i ] && set.insert( str[ i ] ).second == true ) {
                    result.push_back( str[ i ] );
                    used[ i ] = true;
                    dfspermutation( str, result, used );
                    used[ i ] = false;
                    result.pop_back();
                }
            }
        }
        else {
            m_permutation.push_back( result );
        }
    }

    // 剑指 Offer 48. 最长不含重复字符的子字符串
    int lengthOfLongestSubstring( string s ) {

        unsigned int          first = 0, last = 0;
        unordered_set< char > str;
        unsigned int          maxLen = 0;

        while ( last < s.size() ) {
            if ( str.insert( s[ last ] ).second ) {
                last++;
            }
            else {
                str.erase( s[ first ] );
                maxLen = max( maxLen, last - first );
                first++;
            }
        }
        maxLen = max( maxLen, last - first );
        return maxLen;
    }

private:
    vector< string > m_permutation;
};

#endif /*_ABOUT_STRING_*/